import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class BinaryTree {

    public class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public char val;

        public TreeNode (char val) {
            this.val = val;
        }

    }

    public String treeToString (TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();
        treeToStringChild1(root,stringBuilder);
        return stringBuilder.toString();
    }

    private void treeToStringChild(TreeNode root,
                                   StringBuilder stringBuilder) {
        if (root == null) return ;
        stringBuilder.append(root.val);
        if (root.left != null) {
            stringBuilder.append("(");
            treeToStringChild(root.left , stringBuilder);
            stringBuilder.append(")");
        } else {
            if (root.right != null) {
                stringBuilder.append("()");
            } else return ;

        }
        if (root.right == null)  return ;
        else {
            stringBuilder.append("(");
            treeToStringChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }

    }
    private void treeToStringChild1(TreeNode root,
                                         StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        stringBuilder.append(root.val);
        if (root.left != null && root.right != null) {
            stringBuilder.append("(");
            treeToStringChild1(root.left,stringBuilder);
            stringBuilder.append(")");
            stringBuilder.append("(");
            treeToStringChild1(root.right,stringBuilder);
            stringBuilder.append(")");
        } else if (root.left != null) {
            stringBuilder.append("(");
            treeToStringChild1(root.left,stringBuilder);
            stringBuilder.append(")");
        } else if (root.right != null) {
            stringBuilder.append("()");
            stringBuilder.append("(");
            treeToStringChild1(root.right,stringBuilder);
            stringBuilder.append(")");
        } else {
            return ;
        }

    }

    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp == null) {
                break;
            } else {
                queue.offer(tmp.left);
                queue.offer(tmp.right);
            }

        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;

    }

    public void preOrderNor (TreeNode root) {
        if (root == null) return;
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                System.out.println(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
    }

    public void inorderNor (TreeNode root) {
        if (root == null) return;
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);

                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.println(top.val);
            cur = top.right;
        }
    }


}
